/*
题目：有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
 */
public class IsValid {
    //栈
    public static char match(char ch) {
        if (ch == '}') {
            return '{';
        } else if (ch == ']') {
            return '[';
        } else {
            return '(';
        }
    }
    public boolean isValid(String s) {
        char[] stack = new char[s.length()];
        int top = -1; //表示栈顶
        for (int i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);
            if (tmp == '{' || tmp == '[' || tmp == '(') {
                stack[++top] = tmp;
            } else {
                char toMatch = match(tmp);
                if (top == -1 || stack[top] != toMatch) {
                    return false;
                } else {
                    top--;
                }
            }
        }
        return top == -1 ? true : false;
    }
}
